InforLorV4, Main, Exploration, bibRecord, 008896

Recognizing Knödel graphs

Identifieur interne : 008896 ( Main/Exploration ); précédent : 008895; suivant : 008897

Recognizing Knödel graphs

Auteurs : Johanne Cohen [France] ; Pierre Fraigniaud [France] ; Cyril Gavoille [France]

Source :

Discrete mathematics [ 0012-365X ] ; 2002.

RBID : Pascal:02-0414093

Descripteurs français

Pascal (Inist)
- Théorie graphe, Isomorphisme, Radiodiffusion, Algorithme, Unicité solution, Isomorphisme graphe, Graphe Knödel, Graphe Fibonacci, Graphe circulant.
Wicri :
- topic : Radiodiffusion.

English descriptors

KwdEn :
- Algorithm, Broadcasting, Circulant graph, Fibonacci graph, Graph isomorphism, Graph theory, Isomorphism, Knödel graph, Solution uniqueness.
mix :
- anneau à corde, chordal ring, circulant digraph, gossiping., graph isomorphism, graphe circulant, isomorphisme de graphes, échange total, échange total..

Abstract

Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context, In this paper, we show that there exists an O(n log⁵ n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six) A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log⁵ n) time.

Url:

https://hal.inria.fr/inria-00100969

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Recognizing Knödel graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA, Campus Scientifique, BP239</s1>
<s2>54506 Vandœuvre les Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Fraigniaud, Pierre" sort="Fraigniaud, Pierre" uniqKey="Fraigniaud P" first="Pierre" last="Fraigniaud">Pierre Fraigniaud</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Laboratoire de Recherche en Informatique. University Paris-Sud, Bâtiment 490</s1>
<s2>91405 Orsay</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Orsay</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Gavoille, Cyril" sort="Gavoille, Cyril" uniqKey="Gavoille C" first="Cyril" last="Gavoille">Cyril Gavoille</name>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Laboratoire Bordelais de Recherche en Informatique, University Bordeaux I</s1>
<s2>33405 Talence</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Nouvelle-Aquitaine</region>
<region type="old region" nuts="2">Aquitaine</region>
<settlement type="city">Talence</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">02-0414093</idno>
<date when="2002">2002</date>
<idno type="stanalyst">PASCAL 02-0414093 INIST</idno>
<idno type="RBID">Pascal:02-0414093</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000865</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000187</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000776</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000776</idno>
<idno type="wicri:doubleKey">0012-365X:2002:Cohen J:recognizing:knodel:graphs</idno>
<idno type="wicri:Area/Main/Merge">008D61</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00100969</idno>
<idno type="url">https://hal.inria.fr/inria-00100969</idno>
<idno type="wicri:Area/Hal/Corpus">006B80</idno>
<idno type="wicri:Area/Hal/Curation">006B80</idno>
<idno type="wicri:Area/Hal/Checkpoint">005755</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">005755</idno>
<idno type="wicri:doubleKey">0012-365X:2002:Cohen J:recognizing:knodel:graphs</idno>
<idno type="wicri:Area/Main/Merge">008E32</idno>
<idno type="wicri:Area/Main/Curation">008896</idno>
<idno type="wicri:Area/Main/Exploration">008896</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Recognizing Knödel graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA, Campus Scientifique, BP239</s1>
<s2>54506 Vandœuvre les Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Fraigniaud, Pierre" sort="Fraigniaud, Pierre" uniqKey="Fraigniaud P" first="Pierre" last="Fraigniaud">Pierre Fraigniaud</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Laboratoire de Recherche en Informatique. University Paris-Sud, Bâtiment 490</s1>
<s2>91405 Orsay</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Orsay</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Gavoille, Cyril" sort="Gavoille, Cyril" uniqKey="Gavoille C" first="Cyril" last="Gavoille">Cyril Gavoille</name>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Laboratoire Bordelais de Recherche en Informatique, University Bordeaux I</s1>
<s2>33405 Talence</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Nouvelle-Aquitaine</region>
<region type="old region" nuts="2">Aquitaine</region>
<settlement type="city">Talence</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Discrete mathematics</title>
<title level="j" type="abbreviated">Discrete math.</title>
<idno type="ISSN">0012-365X</idno>
<imprint><date when="2002">2002</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Discrete mathematics</title>
<title level="j" type="abbreviated">Discrete math.</title>
<idno type="ISSN">0012-365X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Broadcasting</term>
<term>Circulant graph</term>
<term>Fibonacci graph</term>
<term>Graph isomorphism</term>
<term>Graph theory</term>
<term>Isomorphism</term>
<term>Knödel graph</term>
<term>Solution uniqueness</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Théorie graphe</term>
<term>Isomorphisme</term>
<term>Radiodiffusion</term>
<term>Algorithme</term>
<term>Unicité solution</term>
<term>Isomorphisme graphe</term>
<term>Graphe Knödel</term>
<term>Graphe Fibonacci</term>
<term>Graphe circulant</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Radiodiffusion</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>anneau à corde</term>
<term>chordal ring</term>
<term>circulant digraph</term>
<term>gossiping.</term>
<term>graph isomorphism</term>
<term>graphe circulant</term>
<term>isomorphisme de graphes</term>
<term>échange total</term>
<term>échange total.</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context, In this paper, we show that there exists an O(n log<sup>5</sup>
 n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six) A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log<sup>5</sup>
 n) time.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Aquitaine</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Nouvelle-Aquitaine</li>
<li>Île-de-France</li>
</region>
<settlement><li>Orsay</li>
<li>Talence</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
</region>
<name sortKey="Fraigniaud, Pierre" sort="Fraigniaud, Pierre" uniqKey="Fraigniaud P" first="Pierre" last="Fraigniaud">Pierre Fraigniaud</name>
<name sortKey="Gavoille, Cyril" sort="Gavoille, Cyril" uniqKey="Gavoille C" first="Cyril" last="Gavoille">Cyril Gavoille</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008896 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 008896 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:02-0414093
   |texte=   Recognizing Knödel graphs
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Recognizing Knödel graphs

Recognizing Knödel graphs

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.